import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:二叉树
 * User: LianBao
 * Date: 2024-04-02
 * Time: 18:57
 */
public class BinaryTree {

    //结点,保存了左右孩子
    static class TNode {
        public Object val;//数值
        public TNode left;//左
        public TNode right;//右

        public TNode(Object val) {
            this.val = val;
        }
    }

    public TNode Root;//根结点

    public TNode CreateNode() {
        TNode A = new TNode('A');
        TNode B = new TNode('B');
        TNode C = new TNode('C');
        TNode D = new TNode('D');
        TNode E = new TNode('E');
        TNode F = new TNode('F');
        TNode G = new TNode('G');
        TNode H = new TNode('H');

        A.left = B;
        A.right = C;

        B.left = D;
        B.right = E;

        E.right = H;

        C.left = F;
        C.right = G;

        return A;
    }

    // 前序遍历
    public void preOrder(TNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //非递归前序遍历
    public void preOrderNot(TNode root) {
        Stack<TNode> stack = new Stack<>();
        TNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TNode top = stack.pop();
            cur = top.right;
        }
    }


    // 中序遍历
    public void inOrder(TNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //非递归中序遍历
    public void inOrderNot(TNode root) {
        Stack<TNode> stack = new Stack<>();
        TNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //左走完了
            TNode top = stack.pop();
            //打印
            System.out.print(top.val + " ");
            //再往右
            cur = top.right;
        }
    }

    // 后序遍历
    public void postOrder(TNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //后序遍历非递归
    public void postOrderNot(TNode root) {
        Stack<TNode> stack = new Stack<>();
        TNode cur = root;
        TNode flg = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TNode top = stack.peek();
            if (top.right == null || top.right == flg) {
                stack.pop();
                System.out.print(top.val + " ");
                flg = top;
            } else {
                cur = top.right;
            }
        }
    }

    //求结点个数
    public int Size(TNode root) {
        if (root == null) {
            return 0;
        }
        return Size(root.left) + Size(root.right) + 1;//左边的结点数+根节点+右边的结点数
    }

    //叶子结点个数
    public int getLeafNodeCount(TNode root) {
        if (root == null) {
            return 0;
        }
        //左右都为空才是叶子
        if (root.right == null && root.left == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    //判断二叉树中是否存在值为val的结点,返回该结点,如果没有返回null
    public TNode find(TNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val.equals(val)) {
            return root;
        }

        //找到了要返回!!!
        TNode ret1 = find(root.left, val);

        if (ret1 != null) {
            return ret1;
        }

        ret1 = find(root.right, val);
        return ret1;
    }

    //层序遍历:利用队列实现
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //存储结点的队列
        Queue<TreeNode> queue = new LinkedList<>();
        //1.根节点入队
        queue.offer(root);
        //如果队列不为空,循环下面的操作
        while (!queue.isEmpty()) {

            TreeNode tmp = queue.poll();
            System.out.print(tmp.val + " ");

            if (tmp.left != null) {
                queue.offer(tmp.left);
            }
            if (tmp.right != null) {
                queue.offer(tmp.right);
            }
        }
    }
}